{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum of Minimum Values in All Subarrays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #array #monotonic-stack"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #数组 #单调栈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findMaximums"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #所有子数组最小值中的最大值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个长度为 <code>n</code> 的整数数组 <code>nums</code> ，你需要处理 <code>n</code> 个查询。</p>\n",
    "\n",
    "<p>对于第 <code>i</code> （<code>0 &lt;= i &lt;&nbsp;n</code>）个查询：</p>\n",
    "\n",
    "<ol>\n",
    "\t<li>你需要先找出 <code>nums</code> 的所有长度为 <code>i + 1</code> 的子数组中的<strong> 最小值</strong> 。</li>\n",
    "\t<li>在这些最小值中找出<strong> 最大值</strong> 作为答案。</li>\n",
    "</ol>\n",
    "\n",
    "<p>返回一个 <strong>下标从 0 开始</strong> 的长度为 <code>n</code> 的整数数组 <code>ans</code> ，<code>ans[i]</code> 代表第 <code>i</code> 个查询的答案。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [0,1,2,4]\n",
    "<strong>输出:</strong> [4,2,1,0]\n",
    "<strong>解释:</strong>\n",
    "i = 0:\n",
    "- 大小为 1 的子数组为 [0], [1], [2], [4]\n",
    "- 有最大的最小值的子数组是 [4], 它的最小值是 4\n",
    "i = 1:\n",
    "- 大小为 2 的子数组为 [0,1], [1,2], [2,4]\n",
    "- 有最大的最小值的子数组是 [2,4], 它的最小值是 2\n",
    "i = 2:\n",
    "- 大小为 3 的子数组为 [0,1,2], [1,2,4]\n",
    "- 有最大的最小值的子数组是 [1,2,4], 它的最小值是 1\n",
    "i = 3:\n",
    "- 大小为 4 的子数组为 [0,1,2,4]\n",
    "- 有最大的最小值的子数组是 [0,1,2,4], 它的最小值是 0</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>nums = [10,20,50,10]\n",
    "<strong>输出: </strong>[50,20,10,10]\n",
    "<strong>解释:</strong>\n",
    "i = 0: \n",
    "- 大小为 1 的子数组为 [10], [20], [50], [10]\n",
    "- 有最大的最小值的子数组是 [50], 它的最小值是 50\n",
    "i = 1: \n",
    "- 大小为 2 的子数组为 [10,20], [20,50], [50,10]\n",
    "- 有最大的最小值的子数组是 [20,50], 它的最小值是 20\n",
    "i = 2: \n",
    "- 大小为 3 的子数组为 [10,20,50], [20,50,10]\n",
    "- 有最大的最小值的子数组是 [10,20,50], 它的最小值是 10\n",
    "i = 3: \n",
    "- 大小为 4 的子数组为 [10,20,50,10]\n",
    "- 有最大的最小值的子数组是 [10,20,50,10], 它的最小值是 10</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == nums.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-of-minimum-values-in-all-subarrays](https://leetcode.cn/problems/maximum-of-minimum-values-in-all-subarrays/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-of-minimum-values-in-all-subarrays](https://leetcode.cn/problems/maximum-of-minimum-values-in-all-subarrays/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[0,1,2,4]', '[10,20,50,10]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 单调栈\n",
    "    # 1.首先利用单调栈,计算出每个数作为区间最小值可以往左右两边延拓的长度\n",
    "    # 2.用上述求出的延拓长度L,去更新答案数组ans[L - 1]为其对应最小数字集合(延拓长度为L的数字集合)中最大的一个\n",
    "    # 3.倒序遍历答案数组,将ans[i]更新max(ans[j]),j >= i\n",
    "    # 第三步原因解释: 如果存在数字N1,N2,他们的延拓范围分别为L1,L2,且有N1 < N2,L1 < L2,那么肯定存在长度为L1的子数组且其最小值为N2(只需要截取长度为L2且最小值为N2的子数组即可),因此需要倒序完成最终的更新\n",
    "    # 单调栈求每个值作为最小值的子数组的左右范围，然后用左右范围的差值先试求一部分子数组的最小值的最大值，有的子数组在这一次遍历中是没有的。再倒序用更大范围的最大值更新一遍。例：5，1，1，5 这个数组不会有哪个值会作为子数组长度为3的最小值存在（可以看出来，这两个数值（1和5），要么是范围为4的子数组的最小值，要么是范围为1的子数组的最小值）。所以这种时候，既然子数组长度为2或3的最小值不存在，那沿用更长长度的子数组的最小值是可行的。\n",
    "    def findMaximums(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        stack = [-1]\n",
    "        ans = [0] * n\n",
    "        \n",
    "        for i in range(n):\n",
    "            while stack[-1] != -1 and nums[stack[-1]] > nums[i]:\n",
    "                mn = nums[stack.pop()]\n",
    "                ans[i - stack[-1] - 2] = max(ans[i - stack[-1] - 2], mn)\n",
    "\n",
    "            stack.append(i)\n",
    "\n",
    "        while stack[-1] != -1:\n",
    "            mn = nums[stack.pop()]\n",
    "            ans[n - stack[-1] - 2] = max(ans[n - stack[-1] - 2], mn)\n",
    "        \n",
    "        for i in range(n - 2, -1, -1):\n",
    "            ans[i] = max(ans[i], ans[i + 1])\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximums(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        stack = [-1]\n",
    "        ans = [0] * n\n",
    "        \n",
    "        for i in range(n):\n",
    "            while stack[-1] != -1 and nums[stack[-1]] > nums[i]:\n",
    "                mi = nums[stack.pop()]\n",
    "                \n",
    "                ans[i - stack[-1] - 2] = max(ans[i - stack[-1] - 2], mi)\n",
    "\n",
    "            stack.append(i)\n",
    "        \n",
    "        while stack[-1] != -1:\n",
    "            mi = nums[stack.pop()]\n",
    "            ans[n - stack[-1] - 2] = max(ans[n - stack[-1] - 2], mi)\n",
    "        \n",
    "        for i in range(n - 2, -1, -1):\n",
    "            ans[i] = max(ans[i], ans[i + 1])\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximums(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        stack = [-1]\n",
    "        ans = [0] * n\n",
    "        \n",
    "        for i in range(n):\n",
    "            while stack[-1] != -1 and nums[stack[-1]] > nums[i]:\n",
    "                mi = nums[stack[-1]]\n",
    "                stack.pop()\n",
    "                ans[i - stack[-1] - 2] = max(ans[i - stack[-1] - 2], mi)\n",
    "\n",
    "            stack.append(i)\n",
    "        \n",
    "        while stack[-1] != -1:\n",
    "            mi = nums[stack[-1]]\n",
    "            stack.pop()\n",
    "            ans[n - stack[-1] - 2] = max(ans[n - stack[-1] - 2], mi)\n",
    "        \n",
    "        for i in range(n - 2, -1, -1):\n",
    "            ans[i] = max(ans[i], ans[i + 1])\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximums(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        stack = [-1]\n",
    "        ans = [0] * n\n",
    "        \n",
    "        for i in range(n):\n",
    "            while stack[-1] != -1 and nums[stack[-1]] > nums[i]:\n",
    "                mn = nums[stack.pop()]\n",
    "                ans[i - stack[-1] - 2] = max(ans[i - stack[-1] - 2], mn)\n",
    "\n",
    "            stack.append(i)\n",
    "        \n",
    "        while stack[-1] != -1:\n",
    "            mn = nums[stack.pop()]\n",
    "            ans[n - stack[-1] - 2] = max(ans[n - stack[-1] - 2], mn)\n",
    "        \n",
    "        for i in range(n - 2, -1, -1):\n",
    "            ans[i] = max(ans[i], ans[i + 1])\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def findMaximums(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        ans = [0] * n  # 初始化结果数组\n",
    "        \n",
    "        # 使用单调栈来找出每个元素左边和右边第一个比它小的元素的位置\n",
    "        stack = []\n",
    "        left = [0] * n\n",
    "        right = [n] * n  # 初始化右边界为 n，代表子数组可以到达最后一个元素\n",
    "        \n",
    "        for i in range(n):\n",
    "            while stack and nums[stack[-1]] >= nums[i]:\n",
    "                stack.pop()\n",
    "            left[i] = stack[-1] if stack else -1  # 如果栈为空，左边界是 -1\n",
    "            stack.append(i)\n",
    "        \n",
    "        stack = []\n",
    "        for i in range(n-1, -1, -1):\n",
    "            while stack and nums[stack[-1]] >= nums[i]:\n",
    "                stack.pop()\n",
    "            right[i] = stack[-1] if stack else n  # 如果栈为空，右边界是 n\n",
    "            stack.append(i)\n",
    "        \n",
    "        # 根据左右边界，更新答案\n",
    "        for i in range(n):\n",
    "            length = right[i] - left[i] - 1  # 子数组的长度\n",
    "            ans[length-1] = max(ans[length-1], nums[i])  # 更新答案，找出最大的最小值\n",
    "        \n",
    "        # 对于更短的子数组，如果更长的子数组有更大的最小值，更新答案\n",
    "        for i in range(n-2, -1, -1):\n",
    "            ans[i] = max(ans[i], ans[i+1])\n",
    "        \n",
    "        return ans\n",
    "\n",
    "# 测试代码\n",
    "sol = Solution()\n",
    "print(sol.findMaximums([1, 4, 2, 4]))  # 输出应该是 [1, 4, 2, 4]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximums(self, arr: List[int]) -> List[int]:\n",
    "        n = len(arr)\n",
    "        left = [-1] * n\n",
    "        # find smaller val than cur val\n",
    "        right = [n] * n\n",
    "        # find smaller val than cur val\n",
    "        stack = []\n",
    "        for i, num in enumerate(arr):\n",
    "            while stack and num <= arr[stack[-1]]:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                left[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "            \n",
    "        \n",
    "        stack = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while stack and arr[i] < arr[stack[-1]]:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                right[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "        \n",
    "        count = Counter(arr)\n",
    "        if len(count.keys()) == 1:\n",
    "            return [arr[0]] * n\n",
    "            \n",
    "        res = [-inf] * n\n",
    "        for i, (x, l, r) in enumerate(zip(arr, left, right)):\n",
    "            Len = r - l\n",
    "            for j in range(1, Len):\n",
    "                res[j - 1] = max(res[j-1], x)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximums(self, nums: List[int]) -> List[int]:\n",
    "        nums=[0]+nums+[0]\n",
    "        ans=[0]*(len(nums)-2)\n",
    "        dic=collections.defaultdict(int)\n",
    "        stack=[]\n",
    "        for i in range(len(nums)):\n",
    "            while stack and nums[stack[-1]]>nums[i]:\n",
    "                index=stack.pop()\n",
    "                dic[i-stack[-1]-1]=max(dic[i-stack[-1]-1],nums[index])\n",
    "            stack.append(i)\n",
    "        for k in dic:\n",
    "            ans[k-1]=dic[k]\n",
    "        for i in range(len(ans)-1,0,-1):\n",
    "            ans[i-1]=max(ans[i-1],ans[i])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMaximums(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        left, right = [-1] * n, [n] * n \n",
    "        stack = []\n",
    "        for i, j in enumerate(nums):\n",
    "            while stack and j < nums[stack[-1]]:\n",
    "                right[stack.pop()] = i \n",
    "            if stack:\n",
    "                left[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "        ans = []\n",
    "        ran = Counter()\n",
    "        for i, j in enumerate(nums):\n",
    "            ran[j] = max(ran[j], right[i] - left[i] - 1)\n",
    "        d = 1\n",
    "        for k in sorted(ran.keys(), reverse=True):\n",
    "            while ran[k] >= d:\n",
    "                ans.append(k)\n",
    "                d += 1\n",
    "        return ans \n",
    "\n",
    "\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
